package com.cuz.daileetcode.bat100;

import java.util.*;

public class 无效括号变有效括号的所有可能 {
    public static void main(String[] args) {
        System.out.println(solution1("("));
        System.out.println(new Solution().removeInvalidParentheses("("));
    }

    public static List<String> solution1(String str) {
        if (str == null || str.length() == 0) {
            return Collections.emptyList();
        }
        int left = 0;
        int right = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                left++;
            } else if (str.charAt(i) == ')') {
                right++;
            }
        }
        StringBuilder strNeedDel = new StringBuilder(str);
        int needDelete = Math.abs(right - left);
        if (needDelete == 0) {
            if (isValid(str)) {
                return Collections.singletonList(str);
            } else {
                return Collections.singletonList("");
            }
        }
        Set<String> resSet = new HashSet<>();
        process(strNeedDel, 0, 0, needDelete, resSet, right - left > 0 ? ')' : '(');
        return new ArrayList<>(resSet);
    }

    private static boolean isValid(String str) {
        int leftMoreThan = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '(') {
                leftMoreThan++;
            }
            if (c == ')') {
                leftMoreThan--;
            }
            if (leftMoreThan < 0) {
                return false;
            }
        }
        return true;
    }

    private static void process(StringBuilder strNeedDel, int start, int hasDel, int needDeleteRight, Set<String> resSet, char needDelChar) {
        if (hasDel == needDeleteRight) {
            String res = String.valueOf(strNeedDel);
            if ("".equals(res)){
                return;
            }
            if (isValid(res)){
                resSet.add(res);
            }
            return;
        }
        StringBuilder curOpt = new StringBuilder(strNeedDel);
        for (int i = start; i < curOpt.length(); i++) {
            if (curOpt.charAt(i) == needDelChar) {
                StringBuilder memory = new StringBuilder(curOpt);
                curOpt.deleteCharAt(i);
                process(curOpt, i, hasDel + 1, needDeleteRight, resSet, needDelChar);
                curOpt = memory;
            }
        }
    }


    static class Solution {
        private List<String> res = new ArrayList<String>();

        public List<String> removeInvalidParentheses(String s) {
            int lremove = 0;
            int rremove = 0;

            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    lremove++;
                } else if (s.charAt(i) == ')') {
                    if (lremove == 0) {
                        rremove++;
                    } else {
                        lremove--;
                    }
                }
            }
            helper(s, 0, lremove, rremove);

            return res;
        }

        private void helper(String str, int start, int lremove, int rremove) {
            if (lremove == 0 && rremove == 0) {
                if (isValid(str)) {
                    res.add(str);
                }
                return;
            }

            for (int i = start; i < str.length(); i++) {
                if (i != start && str.charAt(i) == str.charAt(i - 1)) {
                    continue;
                }
                // 如果剩余的字符无法满足去掉的数量要求，直接返回
                if (lremove + rremove > str.length() - i) {
                    return;
                }
                // 尝试去掉一个左括号
                if (lremove > 0 && str.charAt(i) == '(') {
                    helper(str.substring(0, i) + str.substring(i + 1), i, lremove - 1, rremove);
                }
                // 尝试去掉一个右括号
                if (rremove > 0 && str.charAt(i) == ')') {
                    helper(str.substring(0, i) + str.substring(i + 1), i, lremove, rremove - 1);
                }
            }
        }

        private boolean isValid(String str) {
            int cnt = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '(') {
                    cnt++;
                } else if (str.charAt(i) == ')') {
                    cnt--;
                    if (cnt < 0) {
                        return false;
                    }
                }
            }

            return cnt == 0;
        }
    }

}
